// Vahe and Arman
#include "BTreeNode.h"
#include <iostream>

using namespace std;

// struct for leaf node entry
struct BTLeafNode::leafEntry 
{
	RecordId rid;
	int key;
};

// BTLeafNode constructor
BTLeafNode::BTLeafNode()
{
	// initialize the buffer to 0
	memset(buffer, 0, PageFile::PAGE_SIZE);
}
/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::read(PageId pid, const PageFile& pf)
{ 
//	memset(buffer, 0, PageFile::PAGE_SIZE);
	return pf.read(pid, buffer); 
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::write(PageId pid, PageFile& pf)
{ 
	return pf.write(pid, buffer); 
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTLeafNode::getKeyCount()
{
	int keyCount = 0;
	leafEntry* entry = (leafEntry *)buffer;
	while(keyCount < getLeafCapacity())
	{
		if (entry->key == 0) break; // no key 
		keyCount++;
		entry++;
	}
	return keyCount;
}

// getKeyCount helper
int BTLeafNode::getLeafCapacity()
{
  return (PageFile::PAGE_SIZE-sizeof(PageId))/(sizeof(leafEntry));
}

/*
 * Insert a (key, rid) pair to the node.
 * @param key[IN] the key to insert
 * @param rid[IN] the RecordId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTLeafNode::insert(int key, const RecordId& rid)
{
	if(getKeyCount() >= getLeafCapacity()) return RC_NODE_FULL;
	
	int id;
	if (locate(key, id))     // if did not locate the key 
		id = getKeyCount();  // assign getKeyCount to eid

	leafEntry* newEntry = (leafEntry *)buffer + id;
	leafEntry* curEntry = (leafEntry *)buffer + getKeyCount();
	while (curEntry != newEntry) 
	{
		leafEntry* temp = curEntry - 1;
		*curEntry = *temp;
		curEntry = temp;
	}

	// Insert an entry into its correct space
	newEntry->key = key;
	newEntry->rid = rid;
	return 0;
}

/*
 * Insert the (key, rid) pair to the node
 * and split the node half and half with sibling.
 * The first key of the sibling node is returned in siblingKey.
 * @param key[IN] the key to insert.
 * @param rid[IN] the RecordId to insert.
 * @param sibling[IN] the sibling node to split with. This node MUST be EMPTY when this function is called.
 * @param siblingKey[OUT] the first key in the sibling node after split.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::insertAndSplit(int key, const RecordId& rid, 
                              BTLeafNode& sibling, int& siblingKey)
{
    int eid;
	int id = (getKeyCount() + 1) / 2;

	leafEntry extra;
	extra.key = key;
	extra.rid = rid;

	if (locate(extra.key, eid)) return 2;

	// Swapping until we get to split
	while (eid < id) 
	{
		leafEntry* current = (leafEntry *)buffer + eid;
		leafEntry temp = *current;
		*current = extra;
		extra = temp;
		eid++;
	}
 
	if (eid == id) siblingKey = extra.key;
	else siblingKey = ((leafEntry *)buffer + id)->key;

	//Insert extra entry into sibling
	sibling.insert(extra.key, extra.rid);

	eid = id; 
	int count = getKeyCount();
	while (eid < count) 
	{
		leafEntry* current = (leafEntry *)buffer + eid;
		sibling.insert(current->key, current->rid);
		current->key = 0;
		eid++;
	}
	return 0;
}

/*
 * Find the entry whose key value is larger than or equal to searchKey
 * and output the eid (entry number) whose key value >= searchKey.
 * Remeber that all keys inside a B+tree node should be kept sorted.
 * @param searchKey[IN] the key to search for
 * @param eid[OUT] the entry number that contains a key larger than or equalty to searchKey
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::locate(int searchKey, int& eid)
{
	eid = 0;
	while (eid < getKeyCount()) 
	{
		leafEntry* entry = (leafEntry *)buffer + eid;
		if (searchKey > entry->key) eid++;
		else break;
	}

	if (eid == getKeyCount()) 
	{
		eid = -1;
		return 1;
	}
	return 0;
}

/*
 * Read the (key, rid) pair from the eid entry.
 * @param eid[IN] the entry number to read the (key, rid) pair from
 * @param key[OUT] the key from the entry
 * @param rid[OUT] the RecordId from the entry
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::readEntry(int eid, int& key, RecordId& rid)
{
	if (eid < 0 || eid >= getKeyCount()) return 1;
	leafEntry* entry = (leafEntry *)buffer + eid;
	rid = entry->rid;
	key = entry->key;
	return 0;
}

/*
 * Return the pid of the next slibling node.
 * @return the PageId of the next sibling node 
 */
PageId BTLeafNode::getNextNodePtr()
{
	PageId* pid = (PageId *)(buffer + PageFile::PAGE_SIZE) - 1;
	return *pid;
}

/*
 * Set the pid of the next slibling node.
 * @param pid[IN] the PageId of the next sibling node 
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::setNextNodePtr(PageId pid)
{
	PageId* ptr = (PageId *)(buffer + PageFile::PAGE_SIZE) - 1;
	*ptr = pid;
	return 0;
}

// struct for nonleaf node entry
struct BTNonLeafNode::nonleafEntry 
{
	PageId pid;
	int key;
};

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::read(PageId pid, const PageFile& pf)
{
	return pf.read(pid, buffer);
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::write(PageId pid, PageFile& pf)
{ 
	return pf.write(pid, buffer); 
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTNonLeafNode::getKeyCount()
{
	int keyCount = 0;
	nonleafEntry* entry = (nonleafEntry *) buffer;
	while(keyCount < getNonLeafCapacity()) 
	{
		if (entry->key == 0) break;
		keyCount++;
		entry++;
	}
	return keyCount;
}

int BTNonLeafNode::getNonLeafCapacity()
{
	return (PageFile::PAGE_SIZE - sizeof(PageId))/(sizeof(nonleafEntry));
}

/*
 * Insert a (key, pid) pair to the node.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTNonLeafNode::insert(int key, PageId pid)
{ 
	int id;
	if (getKeyCount() >= getNonLeafCapacity()) return RC_NODE_FULL;
	
	//Insert at beginning
	if (locate(key, id)) id = 0;
	// Insert in the slot after the existing entry
	else id++;

	nonleafEntry* newEntry = (nonleafEntry *)buffer + id;
	nonleafEntry* curEntry = (nonleafEntry *)buffer + getKeyCount();
	while (curEntry != newEntry) 
	{
		nonleafEntry* temp = curEntry - 1;
		*curEntry = *temp;
		curEntry = temp;
	}

	// Insert an entry into its correct space
	newEntry->key = key;
	newEntry->pid = pid;
	return 0;
}

RC BTNonLeafNode::readEntry(int eid, PageId& pid) 
{
	if (eid >= getKeyCount()) return 1;
	if (eid < 0) 
	{
		PageId *ptr = (PageId *)(buffer+PageFile::PAGE_SIZE-sizeof(PageId));
		pid = *ptr;
	}
	else 
	{
		nonleafEntry* entry = (nonleafEntry *)buffer + eid;
		pid = entry->pid;
	}
	return 0;
}

/*
 * Insert the (key, pid) pair to the node
 * and split the node half and half with sibling.
 * The middle key after the split is returned in midKey.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @param sibling[IN] the sibling node to split with. This node MUST be empty when this function is called.
 * @param midKey[OUT] the key in the middle after the split. This key should be inserted to the parent node.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::insertAndSplit(int key, PageId pid, BTNonLeafNode& sibling, int& midKey)
{
	int eid;
	int keyCount = getKeyCount();
	
	nonleafEntry extra;
	extra.key = key;
	extra.pid = pid;

	if (locate(extra.key, eid)) return 2;
	eid++;

	int mid = keyCount/2;
	while (eid < mid) 
	{
		nonleafEntry* current = (nonleafEntry *)buffer + eid;
		nonleafEntry temp = *current;
		*current = extra;
		extra = temp;
		eid++;
	}
 
	if (eid != mid)
	{
		nonleafEntry *current = (nonleafEntry *)buffer + mid;
		nonleafEntry temp = *current;
		midKey = current->key;
		*current = extra;
		extra = temp;
	}

	midKey = extra.key;
	eid = mid;
	
	nonleafEntry* current = (nonleafEntry *)buffer + eid;
	sibling.initializeRoot(extra.pid, current->key, current->pid);
	current->key = 0;
	eid++;

	//Insert the entry
	while (eid < keyCount) 
	{
		current = (nonleafEntry *)buffer + eid;
		sibling.insert(current->key, current->pid);
		current->key = 0;
		eid++;
	}
	return 0;
}

/*
 * Given the searchKey, find the child-node pointer to follow and
 * output it in pid.
 * @param searchKey[IN] the searchKey that is being looked up.
 * @param pid[OUT] the pointer to the child node to follow.
 * @return 0 if successful. Return an error code if there is an error.
 
RC BTNonLeafNode::locateChildPtr(int searchKey, PageId& pid)
{
	int slotSize = sizeof(PageId) + sizeof(int);
	int totSize = getKeyCount() * slotSize;
	char* ptr = &(buffer[0]);
	int curr_key;

	ptr += sizeof(int);
	ptr += sizeof(int);

	while(ptr) 
	{
		memcpy(&curr_key, ptr, sizeof(int));
		if(curr_key != 0 && curr_key < searchKey) 
			ptr += sizeof(int);
		else 
		{
			ptr -= sizeof(PageId);
			memcpy(&pid, ptr, sizeof(PageId));
			break;
			}
		ptr += slotSize;
	}
	return 0;  ////////////////////////////// FIXED BELOW
} */

RC BTNonLeafNode::locate(int searchKey, int& eid)
{
	eid = getKeyCount()-1;
	while (eid >= 0) 
	{
		nonleafEntry* entry = (nonleafEntry *)buffer + eid;
		if (searchKey < entry->key) eid--;
		else break;
	}
	
	if (eid == -1) return 1;
	return 0;
}

/*
 * Initialize the root node with (pid1, key, pid2).
 * @param pid1[IN] the first PageId to insert
 * @param key[IN] the key that should be inserted between the two PageIds
 * @param pid2[IN] the PageId to insert behind the key
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::initializeRoot(PageId pid1, int key, PageId pid2)
{
  memset(buffer, 0, PageFile::PAGE_SIZE);
  nonleafEntry root;
  root.key = key;
  root.pid = pid2;

  *((nonleafEntry *)buffer) = root;
  PageId *ptr = (PageId *)(buffer+PageFile::PAGE_SIZE-sizeof(PageId));
  *ptr = pid1;
  return 0;
}
